package monarc.jscheduler.dag.algorithm;

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Vector;

import monarc.jscheduler.dag.graph.Calculus;
import monarc.jscheduler.dag.graph.GPair;
import monarc.jscheduler.dag.graph.Muchie;
import monarc.jscheduler.dag.graph.Nod;
import monarc.jscheduler.dag.graph.PMuchie;
import monarc.jscheduler.dag.graph.Procesor;
import edu.uci.ics.jung.graph.impl.DirectedSparseGraph;
import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;

/**
 * 
 * @author Alexandra Olteanu
 * 
 * Algorithm based on MCP Revisited of Min-You Wu
 *
 */
public class TestAlg extends Algorithm {

	Vector<GPair> alap, blevel,alap_order;
	//StatusCatalog catalog;
	
	/** 
	 * The constructor. 
	 * @param taskuri The Direct Graph of the tasks
	 * @param taskuri The Undirect Graph of the procesors 
	 */ 
	
	/**
	 * constructor MCPvX
	 * @param taskuri graful orientat de taskuri
	 * @param procesoare graful neorientat de procesoare
	 * @param comunicatii
	 */
	public TestAlg( DirectedSparseGraph taskuri, UndirectedSparseGraph procesoare, boolean comunicatii )
	{
		super( taskuri, procesoare, comunicatii );		
	}
	/**
	 * Compute Nod n1
	 * @param n1
	 */
	public void compute( Nod n1 )
	{
		int index = -1;
		double time = -1;	
		for ( int j = 0; j < vProc.size(); j++ )
		{
			double tmp = vProc.get(j).time;				 
			Set pred = n1.getPredecessors();
			Iterator iter = pred.iterator();
			while ( iter.hasNext() )
			{
				Nod nd = (Nod)iter.next();
				if ( nd.indexProc != j && comunicatii )
				{
					Muchie mc = ( Muchie )nd.findEdge( n1 );
					PMuchie pm = ( PMuchie )vProc.get(j).findEdge( vProc.get( nd.indexProc ) );
					if ( tmp < nd.fin + ( mc.data * pm.data ) ) tmp = nd.fin + ( mc.data * pm.data );
				}
				else
					if ( tmp < nd.fin ) tmp = nd.fin;
			}
			if ( time == -1 ) { time = tmp; index = vProc.get(j).index; }
			else if ( time > tmp ) { time = tmp; index = vProc.get(j).index; }
		}
		n1.start = time - vProc.get( index ).time;
		n1.initTime = time;
		n1.sugestie = index;

	}
	
	/**
	 * 
	 */
	public void calcProc()
	{
		Vector<Nod> vNod = new Vector<Nod>();		
		vProc = new Vector<Procesor>();		
		vProc.clear();
		
		//pas 1. Calculeaza timpul ALAP pentru fiecare nod
				
		Calculus cl = new Calculus( taskuri );
		cl.calcFlag();
		cl.mapare();
		cl.calcBLevel();
		cl.calcLcp();
		cl.calcAlap();
		
		blevel = cl.blevel;
		alap = cl.alap;
		
		//construirea vectorului cu Noduri
		Set st = taskuri.getVertices();
		Iterator iter = st.iterator();
		while ( iter.hasNext() )	
			vNod.add( (Nod)iter.next() );
		
		//construirea vectorului cu procesoare
		st = procesoare.getVertices();
		iter = st.iterator();
		while ( iter.hasNext() )
			vProc.add( (Procesor)iter.next() );
		
		//sortarea in functie de indexul procesoarelor
		Collections.sort( vProc, new Comparator<Procesor>() {
			public int compare( Procesor p1, Procesor p2 )
			{
				return ( p1.index - p2.index );				
			}
		});
		
		// initializarea 
		for ( int i = 0; i < vProc.size(); i++ )
		{
			vProc.get(i).nod.clear();
			vProc.get(i).time = 0;			
		}
		
		//sortarea nodurilor in functie de index
		Collections.sort( vNod, new Comparator<Nod>() {
			public int compare( Nod p1, Nod p2 )
			{
				return ( p1.index - p2.index );
			}
		});
		
		//pas 2.
		
		// determin ordonarea in functie de alap
		cl.sortAlap();
		alap_order = cl.alap_order;
		
		//coada de prioritati cu nodurile ordonate (alap_order)
		PriorityQueue<Nod> pq = new PriorityQueue<Nod>(alap_order.size(), new Comparator<Nod>(){
			public int compare( Nod n1, Nod n2 )
			{		
				double m = alap_order.get( n2.index ).value - alap_order.get( n1.index ).value;
				if(m==0){
					compute(n1);
					compute(n2);
					m = n2.initTime - n1.initTime ;
				}
				return (int)( m );			
			}
		});
		
		//initializam indexul procesoarelor ce se doresc a fi asignate
		for ( int i = 0; i < vNod.size(); i++ )
			vNod.get(i).indexProc = -1;
		
		//initializare
		for ( int i = 0; i < vNod.size(); i++ )
			if ( vNod.get(i).flag == 0 )
			{
				vNod.get(i).indexProc = 0;
				vNod.get(i).initTime = 0;
				vNod.get(i).start = 0;
				pq.add( vNod.get(i) );
			}
		
		while ( !pq.isEmpty() )
		{
			Nod node = pq.poll();		
			compute( node );
			vProc.get( node.sugestie ).adaugaNod( node );
			Set succ = node.getSuccessors();
			iter = succ.iterator();
			while ( iter.hasNext() )
			{
				Nod urmas = (Nod)iter.next();
				Set pred = urmas.getPredecessors();
				Iterator it = pred.iterator();
				boolean ready = true;
				while ( it.hasNext() && ready )
				{
					Nod stramos = (Nod)it.next();
					if ( stramos.indexProc == -1 ) ready = false;
				}
				if ( ready ) 
				{		
					compute( urmas );
					pq.add( urmas );
				}
			}
		}		
		
		this.time = vProc.get(0).time;
		for ( int i = 0; i < vProc.size(); i++ )
			if ( this.time < vProc.get(i).time ) this.time = vProc.get(i).time;
		cl.demapare();
	}
}	